1) Field of the Invention
The present invention relates to a process for managing a plurality of data items contained in a plurality of pages which are sequentially arranged in accordance with predetermined relationships. The present invention also relates to a data management apparatus which executes the above process.
2) Description of the Related Art
In data processing systems such as database systems, in which data are written or from which data are deleted, data fragmentation in secondary storage devices increases with the passage of time, and access performance is lowered.
An example of fragmentation which occurs in a B-Tree (balance tree) index (i.e., an index having a structure of a B-Tree) is explained below.
FIG. 10 is a diagram illustrating an example of a B-Tree index for a database. The fragmentation can occur in such an index. As illustrated in FIG. 10, a B-Tree index is comprised of a root page at the top level, index pages at an intermediate level or levels, and leaf pages at the bottom level. That is, the B-Tree index has a tree structure in which a plurality of branches extend from each node to a plurality of descendants of the node at lower levels, and a page is arranged at each node. Information indicating a range of values of keys is stored in each of the root page and the index pages so as to reach a leaf page based on the value of a key. In addition, at least one index data item each of which locates a record corresponding to a key are stored in each leaf page.
In the root page, the range from 0 to 50 is represented by “50”, and the range from 51 to 100 is represented by “100”. Therefore, when the value of a key is “10”, the operation goes to the left index page. Since, in the left index page, the range from 0 to 30 is represented by “30”, and the range from 31 to 50 is represented by “50”, the operation then goes to the leftmost leaf page, which contains index data items “10” and “30”. Thus, a record stored in a secondary storage device and located by the index data item “10” can be accessed.
When a new data item is added to a database which has a B-Tree index, or a data item is deleted from such a database, the B-Tree index per se must be modified accordingly. Examples of conventional methods of modification of a B-Tree index corresponding to addition of a data item to a database or deletion of a data item from a database are explained below.
FIGS. 11(A) through 11(C) are diagrams illustrating an example of a sequence of operations performed for modifying leaf pages in a B-Tree index for a database when a new data item is added to the database. When an index data item 20 having a value “60” is inserted into the leaf page 11 among the sequentially arranged leaf pages 10 to 12 as illustrated in FIG. 11(A), it is necessary to create a new leaf page 13 since there is no available space in the leaf page 11. Next, in order to obtain space for storing the new dynamic image data 20, two index data items respectively having values “80” and “90” in the leaf page 11 are moved to the newly created leaf page 13, as illustrated in FIG. 11(B). Then, the new index data item 20 is written in the obtained space in the leaf page 11, as illustrated in FIG. 11(C).
FIGS. 12(A) and 12(B) are diagrams illustrating an example of a sequence of operations performed for modifying leaf pages in a B-Tree index for a database when an existing data item is deleted from the database. When an index data item having a value “50” is deleted from the leaf page 11 among the sequentially arranged leaf pages 10 to 12 as illustrated in FIG. 12(A), no index data item remains in the leaf page 11 as illustrated in FIG. 12(B). Therefore, the leaf page 11 becomes a degenerated page, and is returned to the system.
As explained above, when a new index data item is inserted into a B-Tree index, often, fragmentation occurs in the leaf pages, i.e., short runs of space are generated in the leaf pages. Each leaf page having a short run of space remains to exist until the space is filled with a new index data item, or an index data item or index data items existing in the leaf page are deleted as illustrated in FIGS. 12(A) and 12(B), and the leaf page is returned as a degenerated page to the system. Further, fragmentation also occurs in the index pages.
Conventionally, when fragmentation occurs, the operation of the system is stopped, and the data items are rearranged by executing an defragmentation program. However, the frequency of occurrence of fragmentation varies with the circumstances. Therefore, a system management person is required to monitor occurrence of fragmentation.
In addition, many database systems and the like which are currently used are operated in a nonstop mode. Therefore, it is difficult to stop the operation of the system for performing defragmentation.